Communicating Lists Over a Noisy Channel

摘要

This work considers a communication scenario where the transmitter chooses alist of size K from a total of M messages to send over a noisy communicationchannel, the receiver generates a list of size L and communication isconsidered successful if the intersection of the lists at two terminals hascardinality greater than a threshold T. In traditional communication systemsK=L=T=1. The fundamental limits of this setup in terms of K, L, T and theShannon capacity of the channel between the terminals are examined.Specifically, necessary and/or sufficient conditions for asymptotically errorfree communication are provided.